import java.util.ArrayList;

/**
 * @author 雷明浩
 * @date 2025/7/4 17:41
 */
public class GenerateParenthesis {
    // 括号生成
    // https://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca?tpId=295&tqId=725&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    private ArrayList<String> ret;
    private StringBuilder path;
    private Integer leftCount = 0;
    private Integer rightCount = 0;
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ret = new ArrayList<String>();
        path = new StringBuilder();
        dfs(n);
        return ret;
    }

    private void dfs(int n) {
        if (leftCount == n && rightCount == n) {
            ret.add(path.toString());
            return;
        }
        if (leftCount < n) {
            leftCount++;
            path.append("(");
            dfs(n);
            leftCount--;
            path.deleteCharAt(path.length()-1);
        }
        if (rightCount < leftCount) {
            rightCount++;
            path.append(")");
            dfs(n);
            rightCount--;
            path.deleteCharAt(path.length()-1);
        }
    }
}